﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution004
{
    //这个思路跟解法三的思路有点相似，排除最小的k/2个数字，k=中位数的位置
    public double FindMedianSortedArrays1(int[] nums1, int[] nums2)
    {
        int n= nums1.Length;
        int m= nums2.Length;

        
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;

        int left1 = 0;
        int right1 = nums1.Length - 1;
       
        int left2 = 0;
        int right2 = nums2.Length - 1;
        //return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
        int leftNum = getKth(nums1,  left1, right1, nums2, left2, right2, left);
        int rightNum = getKth(nums1,  left1, right1, nums2, left2, right2, right);
        Console.WriteLine(leftNum);
        Console.WriteLine(rightNum);
        double res = (leftNum + rightNum) *0.5;
      return  res;

        
    }
    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
    {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1 
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.Min(nums1[start1], nums2[start2]);

        int i = start1 + Math.Min(len1, k / 2) - 1;
        int j = start2 + Math.Min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j])
        {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else
        {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

    public double FindMedianSortedArrays3(int[] nums1, int[] nums2)
    {
        int n = nums1.Length;
        int m = nums2.Length;


        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;

        int left1 = 0;
        int right1 = nums1.Length - 1;

        int left2 = 0;
        int right2 = nums2.Length - 1;
        //return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
        int leftNum = DFS(nums1, nums2, left1, right1, left2, right2, left);
        int rightNum = DFS(nums1, nums2, left1, right1, left2, right2, right);
        Console.WriteLine(leftNum);
        Console.WriteLine(rightNum);
        double res = (leftNum + rightNum) * 0.5;
        return res;


    }
    //这个函数是求第k个小的数字
    int DFS(int[] nums1, int[] nums2, int left1, int right1, int left2, int right2,int k)
    {


        Console.WriteLine(k);


        int len1=right1 - left1+1;
        int len2=right2 - left2+1;

        if (len1 > len2) {
         return   DFS(nums2, nums1, left2, right2, left1, right1, k);
        }

        if (len1 == 0)//数组1空了
        {//中位数在第二个数组里面
            return nums2[left2 + k - 1];
        }
        if (k == 1)//奇数个

            
        {

          
            return Math.Min(nums1[left1], nums2[left2]);
        }

        int mid1= left1+Math.Min(k/2,len1)-1;
        int mid2= left2+Math.Min(k/2,len2)-1;
        int newk1 = k - (mid2 + 1 - left2);//=k-Math.Min(left1+k/2,len1)
        if (nums1[mid1] > nums2[mid2])//把nums1左边的排除掉
            {

           
         
            return DFS(nums1, nums2, left1, right1, mid2 + 1, right2, k - (mid2 + 1 - left2));

        }
            else
            {
            //中位数出现在nums1的左边，nums2的右边
            return DFS(nums1, nums2, mid1 + 1, right1, left2, right2, k - (mid1 + 1 - left1));


        }

    }

    //解法4，分成两份，确保左边和右边的数一样大，而且边界条件，左边的小于等于右边的
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {

        int n = nums1.Length;
        int m = nums2.Length;


        //确保num1的长度小于num2
        if(n>m)
        {
         return   FindMedianSortedArrays(nums2 , nums1);
        }

        
        //while(0<=mid1<=m)
        int left=0, right=n;
        while (left <= right)
        {
            int mid1 = (left+right) / 2;//mid1进行变化
                             //mid2 + mid1 = n - mid1 + m - mid2;//两个左半边加一起，等于总体的一半
                             //2mid2  = n - 2mid1 + m ;
            int mid2 = (n + m + 1) / 2 - mid1;

            //if (Math.Max(nums1[mid1 - 1], nums2[mid2 - 1]) <= Math.Min(nums1[mid1], nums2[mid2]))
            //{
            //    //中位数为 （ Math.Max(nums1[mid1-1], nums2[mid2-1]+Math.Min(nums1[mid1 ], nums2[mid2]))/2
            //}

            //nums1[mid1-1]<=nums2[mid2]&&nums2[mid2-1]<=nums1[mid1 ]
            if (mid1!=0&&mid2!=m&& nums1[mid1 - 1] > nums2[mid2])
            {
                right = mid1 - 1;
                
            }
            else 
            if (mid2!=0&&mid1!=n&&  nums2[mid2 - 1] > nums1[mid1])
            {
                left = mid1 + 1;


            }
            else//边界条件
            {
                int maxleft = 0;//左边的最大值
                int minright = 0;//右边的最小值
               
                if (mid1 == 0){
                    maxleft = nums2[mid2 - 1];
                }else if (mid2 == 0)
                {
                    maxleft = nums1[mid1 - 1];
                }
                else
                {
                    maxleft = Math.Max(nums1[mid1 - 1], nums2[mid2 - 1]);
                }
                if ((m + n) % 2 == 1)//奇数
                {
                    return maxleft;
                }
               

               

                
                if (mid2 == m)
                {
                    minright = nums1[mid1];
                }
                else if (mid1 == n)
                {
                    minright = nums2[mid2];
                }
                else
                {
                    minright = Math.Min(nums1[mid1], nums2[mid2]);
                }
                return (maxleft+minright)*0.5;

            }

        }

        return  0;
        
    }
}
class Program004
{
    static void Main004(string[] args)
    {
        Solution004 solution = new Solution004();
        int[] nums1 = [2], nums2 = [];
        double res= solution.FindMedianSortedArrays(nums1 , nums2);
        Console.WriteLine(res);
    }
}